package com.shm.leetcode;

/**
 * 练习：二叉树上两点的距离
 * 给定一棵二叉树。现在给定 p 和 q，求 p 到 q 的最短距离。
 * 注意：每个节点值均不同。
 *
 * @author SHM
 */
public class DistanceInTree {

    /**
     * 题目解析
     * 在例题里，我们已经有办法求出两个点的最近公共祖先了。而要求最短距离的话，只需要从最近公共祖先出发，分别求到两个点的距离，再相加即可。
     * @param root
     * @param p
     * @param q
     * @return
     */
    public int distanceInTree(TreeNode root, int p, int q) {
        TreeNode ancestor = findAncestor(root,p,q);
        return getDistance(ancestor,p) + getDistance(ancestor,q);
    }
    //找到两节点得最近祖先
    public TreeNode findAncestor(TreeNode root,int p,int q) {
        if(root==null||root.val==p||root.val==q){
            return root;
        }
        TreeNode left = findAncestor(root.left,p,q);
        TreeNode right = findAncestor(root.right,p,q);
        if(left!=null&&right!=null){
            return root;
        }
        return left==null?right:left;
    }
    //计算祖先节点和当前节点之间距离
    public int getDistance(TreeNode ancestor,int value){
        if(ancestor==null){
            return Integer.MIN_VALUE;
        }
        if(ancestor.val==value){
            return 0;
        }
        return Math.max(getDistance(ancestor.left,value)+1,getDistance(ancestor.right,value)+1);
    }
}
